Pumping Lemma

The pumping lemma is a tool for proving a language is not regular. It cannot prove a language is regular -- only that it isn't.

The Idea

Every regular language has a fintie automaton recognising it. If that automaton has p states and you feed it a string of length \geq p, the machine must revisit some state -- creating a loop. That loop can be repeated (pumped) any number of times and the resulting string must still be in the language.

Formal Statement

For any regular language L, there exists a pumping length p \geq 1 such that every string s \in L with |s| \geq p can be split into three parts s = xyz satisfying:

1. |xy| \leq p
2. |y| \geq 1
3. xy^iz \in L for all i \geq 0

The middle piece y is the loop, which can repeated zero or more times and stay in the language.

Using It to Prove Non-Regularity

The proof structure is always a game against an adversary:

1. Assume L is regular, so a pumping length p exists.
2. You pick a string s \in L with |s| \geq p (choose cleverly).
3. The adversary splits s = xyz subject to the constraints above.
4. You show that for some i, xy^iz \notin L.
5. Conclude L is not regular.

Classic Example

Claim: L = \{a^n b^n \mid n \geq 0\} is not regular.

Proof:

• Assume L is regular with pumping length p.
• Choose s = a^p b^p \in L, so |s| = 2p \geq p.
• Any split xyz with |xy| \leq p and |y| \geq 1 means y = a^k for some k \geq 1 (it lies entirely in the a-block).
• Pump with i = 2: xy^2z = a^{p+k}b^p.
• Since k \geq 1, the counts of as and bs differ, so xy^2z \notin L.

Therefore L is not regular. \blacksquare